package dailyTopic;

/**
 * @author zhangmin
 * @create 2021-08-07 11:52
 * 环形数组是否存在循环
 * 1.模拟：next = ((cur + nums[cur]) % n + n ) % n
 * 2.快慢指针
 */
public class circularArrayLoop457 {

    boolean check(int[] nums,int start,int n){
        int curindex=start;
        boolean flag=nums[start]>0;
        //k用来计数扫描长度，若超过n则返回false
        int k=1;
        while (true){
            if (k>n)
                return false;
            int next=((curindex+nums[curindex])%n+n)%n;
            if ((flag&&nums[next]<0)||(!flag&&nums[next]>0)) return false;
            if (next==start){
                return k>1;
            }
            curindex=next;
            k++;
        }
    }
   /* public boolean circularArrayLoop(int[] nums) {
        int n=nums.length;
        for (int i = 0; i < n; i++) {
            if (check(nums,i,n))
                return true;
        }
        return false;
    }*/

   public int getNext(int[] nums,int cur){
       int n=nums.length;
       return ((cur+nums[cur])%n+n)%n;
   }
    public boolean circularArrayLoop(int[] nums) {
        int n=nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i]==0){
                continue;
            }
            int slow=i,fast=getNext(nums,i);
            while (nums[slow]*nums[fast]>0&&nums[slow]*nums[getNext(nums,fast)]>0){
                if (slow==fast){
                    if (slow!=getNext(nums,slow))
                        return true;
                    else break;
                }
                slow=getNext(nums,slow);
                fast=getNext(nums,getNext(nums,fast));
            }
            //无需新建一个数组记录每个点的访问情况，而只需要将原数组的对应元素置零即可
            int add=i;
            while (nums[add]*nums[getNext(nums,add)]>0){
                int t=add;
                add=getNext(nums,add);
                nums[t]=0;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] nums=new int[]{2,-1,1,2,2};
        circularArrayLoop457 object=new circularArrayLoop457();
        System.out.println(object.circularArrayLoop(nums));
    }
}
